﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    public class T_0023_HasCycle
    {
        // 环形链表

        // 给你一个链表的头节点 head ，判断链表中是否有环。
        // 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
        // 如果链表中存在环，则返回 true 。 否则，返回 false 。

        // 提示：
        //  链表中节点的数目范围是[0, 10^4]
        //  -10^5 <= Node.val <= 10^5
        //  pos 为 -1 或者链表中的一个 有效索引 。

        // 进阶：你能用 O(1)（即，常量）内存解决此问题吗？

        public void Test()
        {
            var l1 = new ListNode(1)
            {
                next = new ListNode(3)
                {
                    next = new ListNode(4)
                    {

                    }
                }
            };
            var l2 = new ListNode(2)
            {
                next = l1.next
            };
            l1.next.next.next = l2;
            Console.WriteLine(HasCycle(l1));
            Console.Read();
        }

        // 双指针，快慢指针，若环形必会相遇，否则必有终点（null）
        public bool HasCycle(ListNode head)
        {
            if (head == null)
                return false;
            ListNode sNode = head, fNode = head;
            while (fNode != null && fNode.next != null)
            {
                sNode = sNode.next;
                fNode = fNode.next.next;
                if (sNode == fNode)
                    return true;
            }
            return false;
        }

        // hashSet 最简单，set不允许存在同样的对象
        public bool HasCycle1(ListNode head)
        {
            var set = new HashSet<ListNode>();
            while (head != null)
            {
                if (set.Contains(head))
                    return true;
                set.Add(head);
                head = head.next;
            }
            return false;
        }

        // 内卷！因果切断！每个节点都切断与之后的联系，自己内卷。如果出现某个节点还没有内卷之前下一节点就等于自己，说明绕回去了。
        public bool HasCycle2(ListNode head)
        {
            //如果head为空，或者他的next指向为空，直接返回false
            if (head == null || head.next == null)
                return false;
            //如果出现head.next = head表示有环
            if (head.next == head)
                return true;
            ListNode nextNode = head.next;
            //当前节点的next指向他自己，相当于把它删除了
            head.next = head;
            //然后递归，查看下一个节点
            return HasCycle2(nextNode);
        }

        // 先反转在比较
        public bool HasCycle3(ListNode head)
        {
            ListNode rev = ReverseList(head);
            if (head != null && head.next != null && rev == head)
            {
                return true;
            }
            return false;
        }
        public ListNode ReverseList(ListNode head)
        {
            //新链表
            ListNode newHead = null;
            while (head != null)
            {
                //先保存访问的节点的下一个节点，保存起来
                //留着下一步访问的
                ListNode temp = head.next;
                //每次访问的原链表节点都会成为新链表的头结点，
                //其实就是把新链表挂到访问的原链表节点的
                //后面就行了
                head.next = newHead;
                //更新新链表
                newHead = head;
                //重新赋值，继续访问
                head = temp;
            }
            //返回新链表
            return newHead;
        }
    }
}
